package com.lsa.letcode.the130.surroundedRegions;

import java.util.ArrayDeque;
import java.util.Queue;

public class Solution {
    public void solve(char[][] board) {
    	int rows = board.length;
		if (rows == 0) {
    		return;
    	}
		int cols = board[0].length;
		
		Queue<Pair> q = new ArrayDeque<Pair>();
		for (int c = 0; c < cols; c++) {
			scheduleAcquire(board, 0, c, q);
			scheduleAcquire(board, rows - 1, c, q);
		}
		for (int r = 0; r < rows; r++) {
			scheduleAcquire(board, r, 0, q);
			scheduleAcquire(board, r, cols - 1, q);
		}
		while(!q.isEmpty()) {
			Pair p = q.poll();
			int x = p.x;
			int y = p.y;
			board[x][y] = '1';
			scheduleAcquire(board, x - 1, y, q);
			scheduleAcquire(board, x + 1, y, q);
			scheduleAcquire(board, x, y - 1, q);
			scheduleAcquire(board, x, y + 1, q);
		}
		
		for (int r = 0; r < rows; r++) {
			for (int c = 0; c < cols; c++) {
				if (board[r][c] == '1'){
					board[r][c] = 'O';
				}
				else {
					board[r][c] = 'X';
				}
			}
		}
    }
    
    private void scheduleAcquire(char[][] board, int r, int c, Queue<Pair> q) {
    	int rows = board.length;
    	int cols = board[0].length;
    	if (r < 0 || r > rows - 1 || c < 0 || c > cols - 1) {
    		return;
    	}
    	if (board[r][c] == 'O') {
    		q.add(Pair.create(r, c));
    	}
    }
    
    private static class Pair {
    	int x;
    	int y;
    	
    	Pair(int x, int y) {
			this.x = x;
			this.y = y;
		}

		static Pair create(int x, int y){
    		return new Pair(x, y);
    	}
    }
}